# last changed date: 2020/1/27 16:08

from math import pow, sin, cos, sqrt

class Polynomial:

    def __init__(self, ks):
        self.ks = ks

    def __str__(self):
        s = ""
        i = len(self.ks) - 1
        while i >= 0:
            if self.ks[i] == 0:
                i -= 1
                continue
            s += str(self.ks[i]) + "x^" + str(i) + " "
            i -= 1
        return s

    def __add__(self, other):
        if len(self.ks) > len(other.ks):
            ks = self.ks[:]
            b = other
        else:
            ks = other.ks[:]
            b = self
        i = 0
        for x in b.ks:
            ks[i] += x
            i += 1

        return Polynomial(ks)

    def __sub__(self, other):
        length = max(len(self.ks), len(other.ks))
        ks = [0 for x in range(length)]

        i = 0
        for x in self.ks:
            ks[i] = x
            i = i+1
        i = 0
        for x in other.ks:
            ks[i] = ks[i] - x
            i = i+1

        return Polynomial(ks)

    def __mul__(self, other):
        if type(other) != Polynomial:
            ks = self.ks[:]
            for i in range(len(ks)):
                ks[i] = ks[i] * other

            return Polynomial(ks)

        high = len(self.ks) * len(other.ks)
        ks = [0 for x in range(high)]

        i = 0
        for a in self.ks:
            j = 0
            for b in other.ks:
                ks[i+j] = ks[i+j] + a * b
                j = j+1
            i = i+1

        return Polynomial(ks)

    def __rmul__(self, other):
        ks = self.ks[:]
        for i in range(len(ks)):
            ks[i] = ks[i] * other

        return Polynomial(ks)

    def __truediv__(self, other):
        ks = self.ks[:]
        for i in range(len(ks)):
            ks[i] = ks[i] / other

        return Polynomial(ks)

    def f(self, x):
        y = 0
        _x = 1
        for k in self.ks:
            y = y + k*_x
            _x = _x * x

        return y

    def norm(self, l, r):
        return sqrt(dot_p(self, self, l, r))

    def derivation(self):
        ks = [self.ks[x+1]*(x+1) for x in range(len(self.ks)-1)]
        der = Polynomial(ks)
        return der

    def original(self):
        ks = [0] + [self.ks[x]/(x+1) for x in range(len(self.ks))]
        ori = Polynomial(ks)
        return ori


def dot_p(f, g, l, r):
    sub = f * g
    o = sub.original()
    return o.f(r) - o.f(l)


def integral_poly_sin(k, n, l, r):
    if n == 0:
        # return -k*cos(r) + k*cos(l)
        return k*(-cos(r) + cos(l))
    # return -k*pow(r, n)*cos(r) + k*pow(l, n)*cos(l) + integral_poly_cos(k*n, n-1, l, r)
    return k*(-pow(r, n)*cos(r) + pow(l, n)*cos(l)) + integral_poly_cos(k*n, n-1, l, r)


def integral_poly_cos(k, n, l, r):
    if n == 0:
        # return k*sin(r) - k*sin(l)
        return k*(sin(r) - sin(l))
    # return k*pow(r, n)*sin(r) - k*pow(l, n)*sin(l) - integral_poly_sin(k*n, n-1, l, r)
    return k*(pow(r, n)*sin(r) - pow(l, n)*sin(l)) - integral_poly_sin(k*n, n-1, l, r)

def gsp(vs, l, r):
    e0 = vs[0] / vs[0].norm(l, r)
    es = [e0]
    for i in range(1, len(vs)):
        v = vs[i]
        u = v
        for j in range(i):
            u = u - dot_p(v, es[j], l, r) * es[j]
        e = u / u.norm(l, r)
        es.append(e)

    return es
